import beans.ListNode;
import utils.AlgUtils;

/**
 * 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
 *
 *  
 *
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * 进阶:
 *
 * 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
 *
 * 示例:
 *
 * 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出: 7 -> 8 -> 0 -> 7
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class AddTwoNumbersII {


    int lastSum = 0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode newList = null;
        l1 = reverseLink(l1);
        l2 = reverseLink(l2);
        ListNode last = null;
        while(l1 != null && l2 != null){
            ListNode newNode = addVal(l1.val, l2.val);
            if(newList == null){
                newList = newNode;
                last = newNode;
            } else {
                last.next = newNode;
                last = newNode;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        if(l1 == null && l2 != null){
            while(l2 != null){
                last.next = addVal(l2.val, 0);
                l2 = l2.next;
                last = last.next;
            }
        } else if(l1 != null && l2 == null){
            while(l1 != null){
                last.next = addVal(l1.val,0);
                l1 = l1.next;
                last = last.next;
            }
        }
        if(lastSum == 1){
            last.next = new ListNode(1);
        }
        return reverseLink(newList);
    }

    private ListNode addVal(int a, int b){
        int val = a + b + lastSum;
        if(val >= 10){
            lastSum = 1;
            val = val - 10;
        } else {
            lastSum = 0;
        }
        return new ListNode(val);
    }

    public ListNode reverseLink(ListNode l1){
        ListNode lastNode = l1;
        ListNode nextNode = l1.next;
        l1.next = null;
        while(nextNode != null){
            l1 = nextNode;
            nextNode = nextNode.next;
            l1.next = lastNode;
            lastNode = l1;
        }
        return l1;
    }

    public static void main(String[] args){
        ListNode l1 = AlgUtils.createListNode(new int[]{1});
        ListNode l2 = AlgUtils.createListNode(new int[]{9,9});
        (new AddTwoNumbersII()).addTwoNumbers(l1, l2);
    }
}
